home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / xdme_1.84_src.lha / XDME / Lib / src / AVL.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  19.9 KB  |  962 lines
  1. #define XDME
  2. /******************************************************************************
  3.  
  4.     MODULE
  5.     AVL.c
  6.  
  7.     DESCRIPTION
  8.     simple implementation for (recursive) AVL-trees
  9.     this code can be used for an Amiga(c) shared library
  10.  
  11.     NOTES
  12.  
  13.     if You wanna use that code as a non-shared library
  14.     You might have to modify some "#define"s below; also
  15.     it might be useful to re"#define" A0,A1,A2,D0 and PRE.
  16.     (see below (search for LIB_TYPE))
  17.  
  18.     compile w/ #define ANY_DEBUG to get basic error-checking
  19.            #define AVL_DEBUG to get almost full-featured error-checking
  20.         in either case You must initialize an function-var called
  21.         extern void (*error)(char*, char*, char*);
  22.         which displays our errors;
  23.  
  24.     BUGS
  25.     that implementation on AVL - as is - does not
  26.     create any errormessages; user must make sure,
  27.     not to mess up w/ the trees, nor using two nodes
  28.     of the same name;
  29.  
  30.     TODO
  31.     maybe certain Header structures,
  32.     to support other comparison functions
  33.     and error functions
  34.  
  35.     EXAMPLES
  36.     for AVL-trees there are soooo many examples in other pgms
  37.  
  38.     SEE ALSO
  39.  
  40.     INDEX
  41.  
  42.     HISTORY
  43.     05-07-93 b_noll created
  44.     12-07-93 b_noll added ScanTree, FreeTree
  45.     21-07-93 b_noll changed switch()'s to if()'s
  46.     22-07-93 b_noll disabled all error-calls
  47.     07-10-93 b_noll [re]activated LSON/RSON/NAME/BAL-Macros
  48.     07-11-93 b_noll fixed bug in rem_rek (there were no reports)
  49.     12-05-94 b_noll joined xdme-verion and lib-version
  50.     04-09-94 b_noll BUGFIX in AVL_balance
  51.     16-11-94 b_noll strcmp replaced by external compare function
  52.     $Date: 1994/09/04 17:49:50 $ last update
  53.  
  54. ******************************************************************************/
  55.  
  56. /**************************************
  57.         Includes
  58. **************************************/
  59.  
  60. /* we do not import AVL.h since we did hide tn_Balance from the user there */
  61. #ifndef   AVL_H
  62. /* #include <AVL.h> */
  63. /* #define   AVL_H */
  64. #endif /* AVL_H */
  65.  
  66. #ifndef   EXEC_TYPES_H
  67. #include <exec/types.h>
  68. #endif /* EXEC_TYPES_H */
  69.  
  70. /**************************************
  71.         Global Variables
  72. **************************************/
  73.  
  74. #ifdef XDME
  75. #define   ERROR(x,y,z) error(x,y,z)
  76. extern void error(const char*, ...);
  77. #define   ANY_DEBUG 1
  78. #else
  79. #define   ERROR(x,y,z) if (error) (*error)(x,y,z)
  80. void (*error)(char const *, char const *, char const *) = NULL;
  81. #endif
  82.  
  83.  
  84. /**************************************
  85.         Internal Defines & Structures
  86. **************************************/
  87.  
  88. #ifndef AVL_H
  89. /* redefine it here as we did comment out tn_Balance in AVL.h */
  90. struct TreeNode {
  91.     struct TreeNode * tn_Left;
  92.     struct TreeNode * tn_Right;
  93.     UBYTE          tn_Type;
  94.     BYTE          tn_Balance; /* !PRIVATE! for AVL - do not use it! */
  95. }; /* struct TreeNode */
  96. #endif /* !AVL_H */
  97.  
  98. /**************************************
  99.         Internal Variables
  100. **************************************/
  101.  
  102. /* none */
  103.  
  104. /**************************************
  105.         Internal Prototypes
  106. **************************************/
  107.  
  108. /* static int AVL_rem_rek (struct TreeNode**, struct TreeNode*, int (*compare)(APTR, APTR)); */
  109. /* static int AVL_add_rek (struct TreeNode**, struct TreeNode*, int (*compare)(APTR, APTR)); */
  110. /* static int AVL_balance (struct TreeNode**); */
  111.  
  112. /**************************************
  113.         Macros
  114. **************************************/
  115.  
  116. /**************************************************
  117. **
  118. **  !!    LIB_TYPE  !!
  119. **
  120. **  Change the following lines to switch
  121. **  between a shared-library and a link-library
  122. **  #if 1 -> SHARED
  123. **  #if 0 ->LINK
  124. **
  125. **************************************************/
  126. #if 0
  127. /* SHARED LIB: */
  128. #define AVL_Find     LIBAVL_Find
  129. #define AVL_Append   LIBAVL_Append
  130. #define AVL_Remove   LIBAVL_Remove
  131. #define AVL_FreeTree LIBAVL_FreeTree
  132. #define AVL_ScanTree LIBAVL_ScanTree
  133. #define PRE __asm __saveds
  134. #define A0(x) register __a0 x
  135. #define A1(x) register __a1 x
  136. #define A2(x) register __a2 x
  137. #define D0(x) register __d0 x
  138. #else
  139. /* LINK LIB: */
  140. #define PRE
  141. #define A0(x) x
  142. #define A1(x) x
  143. #define A2(x) x
  144. #define D0(x) x
  145. #endif
  146. /*************************************************/
  147.  
  148. #define INC(x) ++(x)
  149. #define DEC(x) --(x)
  150.  
  151. #define RSON(x) (x)->tn_Right
  152. #define LSON(x) (x)->tn_Left
  153. #define BLNC(x) (x)->tn_Balance
  154.  
  155. #define BAL(x) BLNC(x)
  156.  
  157. #define AVL_SCAN_PRAEFIX  0
  158. #define AVL_SCAN_INFIX      1
  159. #define AVL_SCAN_POSTFIX -1
  160.  
  161. /**************************************
  162.         Implementation
  163. **************************************/
  164.  
  165. #ifdef      ANY_DEBUG
  166. const char* AVL_errdisp1 = "AVL:\n%s!\n";
  167. const char* AVL_errdisp2 = "AVL:\n%s %s!\n";
  168.  
  169. const char* AVL_err_notree = "without a tree";
  170. const char* AVL_err_cotree = "with a corrupt tree";
  171. const char* AVL_err_multi  = "Can not manage multiple nodes\nof same name in one tree";
  172.  
  173. const char* AVL_err_balan  = "called Balance";
  174. const char* AVL_err_rem    = "called Remove";
  175. const char* AVL_err_add    = "called Append";
  176. const char* AVL_err_find   = "called Find";
  177. const char* AVL_err_free   = "called FreeTree";
  178. const char* AVL_err_scan   = "called ScanTree";
  179. #endif /* ANY_DEBUG */
  180.  
  181.  
  182. /*****************************************************************************
  183.  
  184.     NAME
  185.     AVL_balance
  186.  
  187.     PARAMETER
  188.     struct TreeNode** t;
  189.  
  190.     RESULT
  191.     the balance of the new root (? really)
  192.  
  193.     RETURN
  194.     int;
  195.  
  196.     DESCRIPTION
  197.     do a local rebalance if the current node's
  198.     balance is worse than +/- 1
  199.  
  200.     the function is used by AVL_add_rek and
  201.     by AVL_rem_rek on the way back from a
  202.     addition/deletion;
  203.  
  204.     NOTES
  205.     that rebalance affect only up to three nodes;
  206.  
  207.     the function might have been done in a more
  208.     effective way - but I wanna be able to read it
  209.     also in 2 weeks.
  210.  
  211.     BUGS
  212.     none known
  213.  
  214.     EXAMPLES
  215.     why - its hidden
  216.  
  217.     SEE ALSO
  218.     AVL_add_rek, AVL_rem_rek
  219.  
  220.     INTERNALS
  221.     verschachtelte case-construkte,
  222.     um alle normalen Faelle abzudecken,
  223.     die bei AVL_Append und AVL_Remove
  224.     auftreten koennen;
  225.     den Rest habe in mir mit Bildchen
  226.     klargemacht.
  227.  
  228.     Hier mehr zu schreiben hat m.E. keinen
  229.     Sinn, das geht besser mit Papier und Bleistift;
  230.  
  231.     HISTORY
  232.     05-07-93    b_noll  created
  233.  
  234. ******************************************************************************/
  235. static
  236. int AVL_balance (struct TreeNode** t)
  237. {
  238.     struct TreeNode* ot = *t;
  239.     struct TreeNode* lt = LSON(ot);
  240.     struct TreeNode* rt = RSON(ot);
  241.     char         b    = BAL(ot);
  242.  
  243.     if (!ot) {
  244.     ERROR (AVL_errdisp2, AVL_err_balan, "with NULL ptr");
  245.     return 0;
  246.     }
  247.  
  248.  
  249. /* D(bug("AVL:balancing...")); */
  250.  
  251.     switch (b) {
  252.  
  253. #ifdef AVL_DEBUG
  254.     case -1:
  255.     case  0:
  256.     case +1:
  257.     ERROR (AVL_errdisp2, AVL_err_balan, "without need");
  258.     return (b);
  259. #endif /* AVL_DEBUG */
  260.  
  261.     case +2:
  262.     b = BAL(lt);
  263.     switch (b) {
  264.     case -1:
  265. /* D(bug("LR")); */
  266.         rt = RSON(lt);
  267.         *t = rt;
  268.         LSON(ot) = RSON(rt);
  269.         RSON(lt) = LSON(rt);
  270.         LSON(rt) = lt;
  271.         RSON(rt) = ot;
  272.  
  273.  
  274.         b        = BAL(rt);
  275.         BAL(rt) = 0;
  276.         BAL(lt) =  (1-b)/2; /* -:1 0:0 +:0 */
  277.         BAL(ot) = -(1+b)/2; /*   0   0  -1 */
  278.  
  279.         return 0;
  280.  
  281.     case  0:
  282.     case +1: /* LL */
  283. /* D(bug("LL")); */
  284.         *t = lt;
  285.         LSON(ot) = RSON(lt);
  286.         RSON(lt) = ot;
  287.  
  288.         BAL(ot) = -(b-1); /* 0:+1; +1:0 */
  289.         BAL(lt) = +(b-1); /*   -1;    0 */
  290.  
  291.         return b-1;
  292.  
  293. #ifdef AVL_DEBUG
  294.     default:
  295.         ERROR ( AVL_errdisp2, AVL_err_balan, AVL_err_cotree);
  296. #endif /* AVL_DEBUG */
  297.     } /* switch */
  298.  
  299.     break;
  300.  
  301.     case -2:
  302.     b = BAL(rt);
  303.     switch (b) {
  304.     case +1:
  305. /* D(bug("RL")); */
  306.         lt = LSON(rt);
  307.         *t = lt;
  308.         RSON(ot) = LSON(lt);
  309.         LSON(rt) = RSON(lt);
  310.         LSON(lt) = ot;
  311.         RSON(lt) = rt;
  312.  
  313.         b        = BAL(lt);
  314.         BAL(lt) = 0;
  315.         BAL(rt) = -(1+b)/2; /* -:0 0:0 +: */
  316.         BAL(ot) =  (1-b)/2; /*   1   0    */
  317. /* D(bug("b== %d\n",b)); */
  318.  
  319.         return 0;
  320.  
  321.     case  0:
  322.     case -1: /* RR */
  323.  
  324. /* D(bug("RR")); */
  325.         *t = rt;
  326.         RSON(ot) = LSON(rt);
  327.         LSON(rt) = ot;
  328.  
  329.         /* Vorzeichen ??? */
  330.         BAL(ot) = -(b+1); /* 0:-1; -1:0 */
  331.         BAL(rt) = +(b+1); /*   +1;    0 */
  332. /* D(bug("ot%d rt%d\n", -(b+1), (b+1))); */
  333.         return -(b-1);
  334.  
  335. #ifdef AVL_DEBUG
  336.     default:
  337.         ERROR ( AVL_errdisp2, AVL_err_balan, AVL_err_cotree);
  338. #endif /* AVL_DEBUG */
  339.     } /* switch */
  340.     break;
  341.  
  342. #ifdef AVL_DEBUG
  343.     default:
  344.     ERROR ( AVL_errdisp2, AVL_err_balan, AVL_err_cotree);
  345. #endif /* AVL_DEBUG */
  346.     } /* switch */
  347.  
  348.     return 0;
  349. } /* AVL_balance */
  350.  
  351.  
  352.  
  353. /*****************************************************************************
  354.  
  355.     NAME
  356.     AVL_swap_best_right
  357.  
  358.     PARAMETER
  359.     struct TreeNode** swapme;
  360.  
  361.     RESULT
  362.     swapping was necessary and done
  363.  
  364.     RETURN
  365.     BOOL;
  366.  
  367.     DESCRIPTION
  368.     swap the current node (swapme) with the
  369.     leftmost follower/son of its right son
  370.  
  371.     NOTES
  372.     swapping with the rightmost follower of its left son
  373.     would have a similar effect;
  374.  
  375.     perhaps we should first check for a better balance to
  376.     decide which one to use (we have to rename the function then)
  377.  
  378.     BUGS
  379.     none known
  380.  
  381.     EXAMPLES
  382.     why - its hidden
  383.  
  384.     SEE ALSO
  385.     AVL_rem_rek
  386.  
  387.     INTERNALS
  388.     die function ist in 2 Teile zerlegbar:
  389.     die Suche nach dem "optimalen" Nachfolger
  390.     danach das Vertauschen dieses Nachfolgers
  391.     mit dem Root.
  392.  
  393.     HISTORY
  394.     05-07-93    b_noll  created
  395.  
  396. ******************************************************************************/
  397. static
  398. BOOL AVL_swap_best_right (struct TreeNode** swapme)
  399. {
  400.     struct TreeNode* root = *swapme;
  401.     struct TreeNode* curr = root;
  402.     struct TreeNode* prev = NULL;
  403.     struct TreeNode* z;
  404.  
  405. /* D(bug("AVL:swappin' ...")); */
  406.  
  407.     { /* search the mostleft node of the right son */
  408.     if ((curr = RSON(root)) == NULL) {
  409.         return FALSE;
  410.     } /* if */
  411.  
  412.  
  413.     while ((z = LSON(curr))) {
  414.         prev = curr;
  415.         curr = z;
  416.     } /* while */
  417.     }
  418.  
  419.     { /* swap our node and the leftmost right son */
  420.     z = RSON(curr);
  421.     if (prev) {
  422.         LSON(prev) = root;
  423.         RSON(curr) = RSON(root);
  424.     } else {
  425.         RSON(curr) = root;
  426.     } /* if */
  427.  
  428.     RSON(root) = z;
  429.  
  430.     *swapme    = curr;
  431.     LSON(curr) = LSON(root);
  432.     LSON(root) = NULL;
  433.     }
  434.  
  435.  
  436.     { /* swap the balances, too! */
  437.     char bal  = BAL(root);
  438.     BAL(root) = BAL(curr);
  439.     BAL(curr) = bal;
  440.     }
  441.  
  442.     return TRUE;
  443. } /* AVL_swap_best_right */
  444.  
  445.  
  446.  
  447. /*****************************************************************************
  448.  
  449.     NAME
  450.     AVL_rem_rek
  451.  
  452.     PARAMETER
  453.     struct TreeNode** tree;
  454.     struct TreeNode*  obj;
  455.     int (*compare)(A0(APTR),A1(APTR));
  456.  
  457.     RESULT
  458.     The Tree's change of height
  459.  
  460.     RETURN
  461.     int;
  462.  
  463.     DESCRIPTION
  464.     hidden part of AVL_Remove
  465.  
  466.     NOTES
  467.     no security checks involved;
  468.  
  469.     BUGS
  470.     use of 2 nodes w/ the same Id will
  471.     lead into trouble
  472.  
  473.     EXAMPLES
  474.     why - its hidden
  475.  
  476.     SEE ALSO
  477.     AVL_Remove
  478.  
  479.     INTERNALS
  480.     the deletion is done recursively
  481.  
  482.     zunaechst suchen wir nach dem Knoten,
  483.     den wir herausloesen wollen (nur ueber
  484.     check!) bringen den dann an eine
  485.     Position, wo wir loeschen koennen
  486.     und knipsen ihn dort heraus;
  487.     auf dem Rueckweg wird der Baum bei Bedarf
  488.     rebalaniert
  489.  
  490.     HISTORY
  491.     05-07-93    b_noll  created
  492.     21-07-93    b_noll  switch(strcmp) -> if(diff) to handle w/ SAS
  493.     16-11-94    b_noll  strcmp replaced by external compare function
  494.  
  495. ******************************************************************************/
  496. static
  497. int AVL_rem_rek (struct TreeNode** tree, struct TreeNode* obj, int (*compare)(A0(APTR),A1(APTR)))
  498. {
  499.  
  500.     struct TreeNode* n     = *tree;
  501.     int          diff;
  502.  
  503.     if (!n) {
  504. #ifdef      ANY_DEBUG
  505.     ERROR ( AVL_errdisp1, "Can't remove non-added node", NULL);
  506. #endif /* ANY_DEBUG */
  507.     return 0;
  508.     } /* if */
  509.  
  510.     if ((diff = compare(obj,n)) == 0) {
  511.     if (n != obj) {
  512. #ifdef      ANY_DEBUG
  513.         ERROR ( AVL_errdisp1, AVL_err_multi, NULL);
  514. #endif /* ANY_DEBUG */
  515.         return 0;
  516.     } /* if */
  517.  
  518.     if (AVL_swap_best_right(tree)) { /* noch nich' am boden */
  519.         n = *tree;
  520.         goto remright;        /* ab hier koennte es beschleunigt werden */
  521.     } else {            /* schon am rand - abschneiden */
  522.         *tree = LSON(n);        /* PATCH_NULL BUGFIX [07 Nov 1993] : Right <-> Left */
  523.         return 1;
  524.     } /* if am rand */
  525.  
  526.     } else if (diff > 0) {
  527. remright:
  528.     if ( AVL_rem_rek(&RSON(n), obj, compare) ) {
  529.         INC(BAL(n));
  530.         if (BAL(n) == 2) {
  531.         AVL_balance(tree);
  532.         } /* if */
  533.         return !BAL(*tree);
  534.     } /* if */
  535.     return 0;
  536.  
  537.     } else {
  538.     if ( AVL_rem_rek(&LSON(n), obj, compare) ) {
  539.         DEC(BAL(n));
  540.         if (BAL(n) == -2) {
  541.         AVL_balance(tree);
  542.         } /* if */
  543.         return !BAL(*tree);
  544.     } /* if */
  545.     return 0;
  546.  
  547.     } /* if */
  548. } /* AVL_rem_rek */
  549.  
  550.  
  551. /*****************************************************************************
  552.  
  553.     NAME
  554.     AVL_add_rek
  555.  
  556.     PARAMETER
  557.     struct TreeNode** tree;
  558.     struct TreeNode*  obj;
  559.     int (*compare)(A0(APTR),A1(APTR));
  560.  
  561.     RESULT
  562.     The Tree's change of height
  563.  
  564.     RETURN
  565.     int;
  566.  
  567.     DESCRIPTION
  568.     hidden part of AVL_Append
  569.  
  570.     NOTES
  571.     no security checks involved;
  572.  
  573.     BUGS
  574.     none known
  575.  
  576.     EXAMPLES
  577.     why - its hidden
  578.  
  579.     SEE ALSO
  580.     AVL_Append
  581.  
  582.     INTERNALS
  583.     the addition is done recursively
  584.  
  585.     wir gehen solange nach unten, bis
  586.     wir auf ein NIL-kind stossen und
  587.     haengen unseren Node dorthin;
  588.     auf dem Rueckweg wird der Baum bei Bedarf
  589.     rebalaniert
  590.  
  591.     HISTORY
  592.     05-07-93    b_noll  created
  593.     21-07-93    b_noll  switch(strcmp) -> if(diff) to handle w/ SAS
  594.     16-11-94    b_noll  strcmp replaced by external compare function
  595.  
  596. ******************************************************************************/
  597. static
  598. int AVL_add_rek (struct TreeNode** tree, struct TreeNode* obj, int (*compare)(A0(APTR),A1(APTR)))
  599. {
  600.     struct TreeNode* n     = *tree;
  601.     int          diff;
  602.  
  603.     if (!n) {
  604.     *tree = obj;
  605.     RSON(obj) = NULL;
  606.     LSON(obj) = NULL;
  607.     BAL(obj)  = 0;
  608.     return 1;
  609.     } /* if */
  610.  
  611.     if ((diff = compare(obj, n)) == 0) {
  612. #ifdef     ANY_DEBUG
  613.     ERROR ( AVL_errdisp1, AVL_err_multi, NULL);
  614. #endif /* ANY_DEBUG */
  615.     return 0;
  616.  
  617.     } else if (diff > 0) {
  618.     if (AVL_add_rek(&RSON(n), obj, compare)) {
  619.         DEC(BAL(n));
  620.         if (BAL(n) == -2) {
  621.         AVL_balance(tree);
  622.         } else {
  623.         return BAL(n);
  624.         } /* if */
  625.     } /* if */
  626.     return 0;
  627.  
  628.     } else {
  629.     if (AVL_add_rek(&LSON(n), obj, compare)) {
  630.         INC(BAL(n));
  631.         if (BAL(n) == 2) {
  632.         AVL_balance(tree);
  633.         } else {
  634.         return BAL(n);
  635.         } /* if */
  636.     } /* if */
  637.     return 0;
  638.  
  639.     } /* if */
  640. } /* AVL_add_rek */
  641.  
  642.  
  643.  
  644. /*****************************************************************************
  645.  
  646.     NAME
  647.     AVL_Find
  648.  
  649.     PARAMETER
  650.     A0( struct TreeNode** tree     );
  651.     A1( APTR              userdata );
  652.     A2( int (*check)(A0(APTR),A1(APTR)));
  653.  
  654.     RESULT
  655.     the treenode, that matches name - if exists
  656.  
  657.     RETURN
  658.     PRE struct TreeNode*;
  659.  
  660.     DESCRIPTION
  661.     search for name in the tree
  662.  
  663.     NOTES
  664.     check() must return 0 on match, <0 and >0 like
  665.     compare in the insert/remove functions ...
  666.     its 1st arg is a TreeNode, the 2nd is userdata
  667.  
  668.     ** Be Aware - You must give the Tree's ADDRESS **
  669.     (that would not have been necessary, here, but
  670.     so I can show a little bit more consistency,
  671.     since AVL_Append and AVL_Remove do need it)
  672.  
  673.     BUGS
  674.     none known
  675.  
  676.     EXAMPLES
  677.  
  678.     SEE ALSO
  679.     AVL_Append, AVL_Remove
  680.  
  681.     INTERNALS
  682.     search is done iteratively
  683.  
  684.     HISTORY
  685.     05-07-93    b_noll  created
  686.  
  687. ******************************************************************************/
  688.  
  689. PRE struct TreeNode* AVL_Find (A0( struct TreeNode** tree ), A1( APTR userdata ), A2( int (*check)(A0(APTR),A1(APTR))))
  690. {
  691.     int          diff;
  692.     struct TreeNode* n;
  693.  
  694.     if (!tree) {
  695. #ifdef     AVL_DEBUG
  696.     ERROR ( AVL_errdisp2, AVL_err_find, AVL_err_notree);
  697. #endif /* AVL_DEBUG */
  698.     return NULL;
  699.     } /* if */
  700.  
  701.     n = *tree;
  702.  
  703.     while ((n != NULL) && (diff = check(n,userdata))) {
  704.     if (diff > 0) {
  705.         n = RSON(n);
  706.     } else {
  707.         n = LSON(n);
  708.     } /* if */
  709.     } /* while */
  710.  
  711.     return n;
  712. } /* AVL_Find */
  713.  
  714.  
  715.  
  716. /*****************************************************************************
  717.  
  718.     NAME
  719.     AVL_Remove
  720.  
  721.     PARAMETER
  722.     A0( struct TreeNode** tree     );
  723.     A1( struct TreeNode*  remove   );
  724.     A2( int (*compare)(A0(APTR),A1(APTR)));
  725.  
  726.     RESULT
  727.     *tree == the tree after Deleting the obsolete node
  728.  
  729.     RETURN
  730.     PRE struct TreeNode*;
  731.  
  732.     DESCRIPTION
  733.     Remove a node from an avl-tree; the right
  734.     position is searched with compare()
  735.  
  736.     NOTES
  737.     U first have to search for the node which
  738.     is to be deleted e.g.:
  739.     AVL_Rem(&tree, FindTreeNode(&tree, name ));
  740.  
  741.     ** Be Aware - You must give the Tree's ADDRESS **
  742.  
  743.     BUGS
  744.     none known
  745.  
  746.     EXAMPLES
  747.  
  748.     SEE ALSO
  749.     AVL_Find, AVL_Append, AVL_rem_rek
  750.  
  751.     INTERNALS
  752.     the deletion is actually done by AVL_rem_rek
  753.     AVL_Remove is only something like a security-
  754.     interface
  755.  
  756.     HISTORY
  757.     05-07-93    b_noll  created
  758.     16-11-94    b_noll  added compare
  759.  
  760. ******************************************************************************/
  761.  
  762. PRE struct TreeNode* AVL_Remove (A0( struct TreeNode** tree ), A1( struct TreeNode* remove ), A2( int (*compare)(A0(APTR),A1(APTR))))
  763. {
  764.     if (!tree) {
  765. #ifdef     AVL_DEBUG
  766.     ERROR ( AVL_errdisp2, AVL_err_rem, AVL_err_notree);
  767. #endif /* AVL_DEBUG */
  768.     return NULL;
  769.     } /* if */
  770.  
  771.     if (!(*tree))
  772.     return NULL;
  773.  
  774.     if (remove)
  775.     AVL_rem_rek (tree, remove, compare);
  776.  
  777.     return *tree;
  778. } /* AVL_Remove */
  779.  
  780.  
  781.  
  782.  
  783. /*****************************************************************************
  784.  
  785.     NAME
  786.     AVL_Append
  787.  
  788.     PARAMETER
  789.     A0( struct TreeNode** tree     );
  790.     A1( struct TreeNode*  new      );
  791.     A2( int (*compare)(A0(APTR),A1(APTR)));
  792.  
  793.     RESULT
  794.     *tree == the tree after Appending the new node
  795.  
  796.     RETURN
  797.     PRE struct TreeNode*;
  798.  
  799.     DESCRIPTION
  800.     Append a new node to an avl-tree; the right
  801.     position is calculated with compare()
  802.  
  803.     NOTES
  804.     U cannot define two nodes with the same
  805.     name in one tree
  806.  
  807.     ** Be Aware - You must give the Tree's ADDRESS **
  808.  
  809.     BUGS
  810.     none known
  811.  
  812.     EXAMPLES
  813.  
  814.     SEE ALSO
  815.     AVL_Remove, AVL_add_rek
  816.  
  817.     INTERNALS
  818.     the Addition is actually done by AVL_add_rek
  819.     AVL_Append is only something like a security-
  820.     interface
  821.  
  822.     HISTORY
  823.     05-07-93    b_noll  created
  824.     16-11-94    b_noll  added compare
  825.  
  826. ******************************************************************************/
  827.  
  828. PRE struct TreeNode* AVL_Append (A0( struct TreeNode** tree ), A1( struct TreeNode* new ), A2( int (*compare)(A0(APTR),A1(APTR))))
  829. {
  830.     if (!tree) {
  831. #ifdef     AVL_DEBUG
  832.     ERROR ( AVL_errdisp2, AVL_err_add, AVL_err_notree);
  833. #endif /* AVL_DEBUG */
  834.     return NULL;
  835.     } /* if */
  836.  
  837.     if (new)
  838.     AVL_add_rek (tree, new, compare);
  839.  
  840.     return *tree;
  841. } /* AVL_Append */
  842.  
  843.  
  844.  
  845. /*****************************************************************************
  846.  
  847.     NAME
  848.     AVL_FreeTree
  849.  
  850.     PARAMETER
  851.     A0( struct TreeNode** tree );
  852.     A1( void (*freefunc)(A0( APTR )) );
  853.  
  854.     RESULT
  855.     -/-
  856.  
  857.     RETURN
  858.     PRE void
  859.  
  860.     DESCRIPTION
  861.     free all entries of a certain tree;
  862.  
  863.     NOTES
  864.     ** Be Aware - You must give the Tree's ADDRESS **
  865.  
  866.     ** Be Aware - You must not delete a partial tree,
  867.                     but only whole trees **
  868.  
  869.     BUGS
  870.     none known
  871.  
  872.     EXAMPLES
  873.  
  874.     SEE ALSO
  875.  
  876.     INTERNALS
  877.     the tree is completely deleted, without respect to
  878.     any balance; we expect to call that function only on
  879.     root-nodes;
  880.  
  881.     HISTORY
  882.     12-07-93    b_noll  created
  883.  
  884. ******************************************************************************/
  885.  
  886. PRE void AVL_FreeTree (A0( struct TreeNode** tree ), A1( void (*freefunc)(A0( APTR )) ))
  887. {
  888.     if (tree) {
  889.     if (*tree) {
  890.         AVL_FreeTree(&(LSON(*tree)),  freefunc);
  891.         AVL_FreeTree(&(RSON(*tree)), freefunc);
  892.         (*freefunc) (*tree);
  893.         *tree = NULL;
  894.     } /* if */
  895. #ifdef     AVL_DEBUG
  896.     } else {
  897.     ERROR ( AVL_errdisp2, AVL_err_free, AVL_err_notree);
  898. #endif /* AVL_DEBUG */
  899.     } /* if */
  900. } /* AVL_FreeTree */
  901.  
  902.  
  903.  
  904. /*****************************************************************************
  905.  
  906.     NAME
  907.     AVL_ScanTree
  908.  
  909.     PARAMETER
  910.     A0( struct TreeNode** tree );
  911.     A1( void (*scanfunc)(A0( APTR )) );
  912.     D0( char mode );
  913.  
  914.     RESULT
  915.     -/-
  916.  
  917.     RETURN
  918.     PRE void
  919.  
  920.     DESCRIPTION
  921.     call a certain function on all nodes of a certain tree
  922.  
  923.     NOTES
  924.     ** Be Aware - You must give the Tree's ADDRESS **
  925.  
  926.     BUGS
  927.  
  928.     EXAMPLES
  929.  
  930.     SEE ALSO
  931.  
  932.     INTERNALS
  933.  
  934.     HISTORY
  935.     12-07-93    b_noll  created
  936.  
  937. ******************************************************************************/
  938.  
  939. PRE void AVL_ScanTree (A0( struct TreeNode** tree ), A1( void (*scanfunc)(A0( APTR )) ), D0( char mode ))
  940. {
  941.     if (tree) {
  942.     if (*tree) {
  943.         if (mode == AVL_SCAN_PRAEFIX) (*scanfunc) (*tree);
  944.         AVL_ScanTree(&(LSON(*tree)),  scanfunc, mode);
  945.         if (mode == AVL_SCAN_INFIX  ) (*scanfunc) (*tree);
  946.         AVL_ScanTree(&(RSON(*tree)), scanfunc, mode);
  947.         if (mode == AVL_SCAN_POSTFIX) (*scanfunc) (*tree);
  948.     } /* if */
  949. #ifdef     AVL_DEBUG
  950.     } else {
  951.     ERROR ( AVL_errdisp2, AVL_err_scan, AVL_err_notree);
  952. #endif /* AVL_DEBUG */
  953.     } /* if */
  954. } /* AVL_ScanTree */
  955.  
  956.  
  957.  
  958.  
  959. /******************************************************************************
  960. *****  END AVL.c
  961. ******************************************************************************/
  962.